Scan design is a widely used design for testability technique. According to this technique, memory elements (flip-flops) are connected into a shift register scan chain during the test mode and hence, can be directly controlled and observed. When all of the flip-flops in a circuit are included in the scan chain (full scan design), combinational test generation methods are sufficient. However, full scan design may entail unacceptable penalties in terms of area overhead and performance degradation. An alternative is to select a subset of the flip-flops for inclusion in the scan chain (partial scan). Thus, both area and performance penalties can be significantly reduced, but the partial scan circuit requires the use of sequential test generation methods.
Various approaches for selecting the flip-flops used for partial scan are classified as testability analysis based, test generation based and structural analysis based. Cheng and Agrawal in an article entitled "A Partial Scan Method for Sequential Circuits with Feedback" in IEEE Transactions on Computing, vol 39, pages 544 to 548, August 1990, disclosed that the feedback cycles among flip-flops are mainly responsible for test generation complexity. They empirically observed that partial scan circuits with self-loops but without feedback cycles are easier to test than circuits that have long feedback cycles. A self-loop refers to a situation where the output of a flip-flop, after passing through combinational logic, feeds back as an input into the same flip-flop. Allowing self-loops in the partial scan circuit is particularly attractive since a large number of flip-flops in commercially used designs have self-loops. Therefore, the scan overhead will be high if it were deemed necessary to break all feedback loops.
The approach proposed by Cheng and Agrawal translates to a graph problem. Let V.sub.1, . . . , V.sub.n be the set of flip-flops in the circuit. The structural dependencies among flip-flops can be represented by a directed graph, called the S-graph. This graph has as many vertices as the number of flip-flops in the circuit. There exists an arc from vertex v.sub.i to vertex v.sub.j if there is a combinational path from flip-flop v.sub.i to flip-flop v.sub.j. Also, there is an arc from vertex v.sub.i to itself (self-loop) if there is a combinational path from flip-flop v.sub.i to itself. The flip-flop selection problem is equivalent to the problem of finding the smallest set of vertices whose removal makes the S-graph acyclic. This is referred to as the minimum feedback vertex set (MFVS) problem. If self-loops are permitted in the partial scan circuit, then the self-loops in the S-graph may be disregarded when computing the MFVS. There are situations where it may be desirable to also eliminate self-loops. Since the vertices with self-loops must belong to the MFVS, these vertices can be deleted first from the S-graph. The remaining S-graph is smaller and its MFVS, which can be solved in accordance with the teachings of the present invention, is an easier problem to solve.
The MFVS problem belongs to the class of NP-hard problems. Algorithms to solve this problem were proposed even before complexity theoretic notions were developed. A known non-trivial exact algorithm is described in an article by Smith and Walford entitled "The Identification of Minimum Feedback Vertex set of a Directed Graph" in IEEE Transaction on Circuits and Systems, vol 22, pages 9 to 14, January 1975. Their method is practical only for small graphs. Several heuristic methods have been developed for large problems but these methods cannot ascertain the closeness of the solution to the optimal solution. It is possible that the problem of finding a solution that is provably within a constant factor of the optimal solution might be NP-hard.